/* 矩阵乘法
* 1.
    F(n) = [f(n), f(n+1), S(n)]
    F(n+1) = [f(n+1), f(n+2), S(n+1)]
*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define int long long

const int N = 3;
int n, m; 

void mul(int c[], int a[], int b[][N])
{
    int temp[N] = {0};
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            temp[i] = (temp[i] + 1ll*a[j]*b[j][i])%m;

    memcpy(c, temp, sizeof temp);
}


void mul(int c[][N], int a[][N], int b[][N])
{
    int  temp[N][N];
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            for(int k = 0; k < N; k++)
                temp[i][j] = (temp[i][j] + 1ll*a[i][k]*b[k][j]) % m;

    memcpy(c, temp, sizeof temp);

}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
    #else
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n >> m;

    int f1[3] {1, 1, 1};
    int a[N][N] ={
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1}
    };

    n--;
    while(n)
    {
        if(n&1) mul(f1, f1, a); // f1 = f1 * a -> res = res * a
        mul(a, a, a); // a = a * a -> base = base * base
        n >>= 1;
    }
    cout << f1[2] << endl;
}
